"""
给你二叉树的根节点root 和一个表示目标和的整数targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和targetSum 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
示例 3：
输入：root = [1,2], targetSum = 0
输出：false

链接：https://leetcode-cn.com/problems/path-sum
"""

from mode import *


class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        def dfs(node, temp, target):
            if node is None:
                return
            target = target - node.val
            temp.append(node.val)
            if target == 0 and node.left is None and node.right is None:
                res.append(list(temp))
            dfs(node.left, temp, target)
            dfs(node.right, temp, target)
            temp.pop()

        res = []
        temp = []

        dfs(root, temp, targetSum)

        return True if len(res) > 0 else False


class Solution1:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        res = []

        def dfs(node, tar):
            if not node:
                return

            tar += node.val
            if tar == targetSum and not node.left and not node.right:
                res.append(node.val)
            dfs(node.left, tar)
            dfs(node.right, tar)
            tar -= node.val

        dfs(root, 0)
        return True if len(res) > 0 else False


if __name__ == "__main__":
    """
                5
          4           8
      11          13      4           
    7    2                  1
    """
    n = TreeNode(5)
    n1 = TreeNode(4)
    n2 = TreeNode(8)
    n3 = TreeNode(11)
    n4 = TreeNode(13)
    n5 = TreeNode(4)
    n6 = TreeNode(7)
    n7 = TreeNode(2)
    n8 = TreeNode(1)
    n.left = n1
    n.right = n2
    n1.left = n3
    n2.left = n4
    n2.right = n5
    n3.left = n6
    n3.right = n7
    n5.right = n8
    PrintTree(n)

    A = Solution()
    print(A.hasPathSum(n, 22))

    A = Solution1()
    print(A.hasPathSum(n, 22))
